class Solution(object):
    def search(self, nums, target):
        def findPeak(begin, end):
            if begin==end:
                return begin
            elif begin+1==end:
                return begin if nums[begin]>nums[end] else end
            if nums[begin]<nums[end]:
                return end
            mid = (begin+end)//2
            if nums[mid]>nums[begin]:
                return findPeak(mid, end)
            elif nums[mid]<nums[end]:
                return findPeak(begin,mid-1)
            else:
                peak1 = findPeak(begin, mid)
                peak2 = findPeak(mid+1, end)
                return peak1 if nums[peak1]>nums[peak2] else peak2
        def findValley(begin, end):
            if begin==end:
                return begin
            if begin+1==end:
                return end if nums[end]<nums[begin] else begin
            if nums[begin]<nums[end]:
                return begin
            mid=(begin+end)//2
            if nums[mid]>nums[begin]:
                return findValley(mid+1, end)
            elif nums[mid]<nums[end]:
                return findValley(begin, mid)
            else:
                valley1 = findValley(begin, mid-1)
                valley2 = findValley(mid, end)
                return valley2 if nums[valley2]<nums[valley1] else valley1
        begin, end = None, None
        if nums[0]<nums[-1]:
            begin = 0
            end = len(nums)-1
        else:
            peak = findPeak(0, len(nums)-1)
            valley = findValley(0, len(nums)-1)
            print(peak, valley)
            if peak<valley:
                if target>=nums[0]:
                    begin, end = 0, peak
                elif target<=nums[-1]:
                    begin, end = peak+1, len(nums)-1
                else:
                    return False
            else:
                begin=valley
                end=peak
        while begin<=end:
            mid = (begin+end)//2
            if nums[mid]<target:
                begin=mid+1
            elif nums[mid]>target:
                end=mid-1
            else:
                return True
        return False

print(Solution().search([1,2,2,2,0], 0))